1. Field of the Invention
The present invention relates to an integrated circuit placement method for an integrated circuit, and more specifically to an integrated circuit placement method to obtain an optimum placement when a mini-cut method is applied.
With the remarkable progress of the recent circuit technologies, density of a chip has been strikingly increased and the size of a chip has been enlarged considerably. Thus, the number of cells contained in a chip of an integrated circuit is actively increasing. Therefore, it becomes more and more difficult to obtain an optimum placement in such an integrated circuit. Under the conditions, a new effective placement method is required to obtain the optimum solution.
2. Description of the Related Art
A mini-cut method is used as one of the cell placement algorithms for an integrated circuit. According to the mini-cut method, a cut line is set, and the circuit is divided into blocks so as to minimize number of nets (hereinafter referred to as cut size) that interconnect cells in both blocks. The final cell placement is obtained by repeatedly setting additional cut lines.
According to the mini-cut method, cells are moved between blocks based on the cell-gain concept. A cell-gain is defined as the cut size decreased when the cell is moved to another block.
If a cell encompassed by bold lines as shown in the part (a) of FIG. 1 is moved to another block, then the net to the cell becomes uncut, thereby the cell-gain of the cell is g=1. On the other hand, if a cell shown as being encompassed by fine lines is moved, the net is kept uncut, thereby the cell-gain of the cell is 0. In (c) in FIG. 1, if a cell is moved, the cell-gain is -1 because the cut size is increased.
The mini-cut method has a cell move according to a cell-gain concept to reduce the cut size. Moving a cell and re-evaluating the cell-gain are repeatedly processed until the cut size will not be decreased. However, during the execution of the mini-cut method, if a net remains uncut from the beginning to the end of the process, an achieved stable state is not necessarily optimum, but can be a so-called "local minimum".
FIG. 2 shows an example of such a net. In a state in which a plurality of cells exist on both sides of the cut line the cell-gain does not change, even if a single cell is moved beyond the cut line to another block. If such a net exists in an initial placement, the net possibly remains uncut until the end of the process, and may incur a local minimum.
Conventionally, the initial solution is altered and the mini-cut method is started from the very beginning if it is determined that a stable state achieved by performing the mini-cut method only indicates a local minimum.
However, if the number of cells of an integrated circuit becomes large, then the mini-cut method can result in a local minimum. Therefore, multiple initial solutions are required to obtain better results. There also is a problem that the optimum cell placement cannot be obtained due to repeated local minimums determined however often the initial placement may be altered.